//给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
//
// 差值是一个正数，其数值等于两值之差的绝对值。
//
//
//
// 示例 1：
//
//
//输入：root = [4,2,6,1,3]
//输出：1
//
//
// 示例 2：
//
//
//输入：root = [1,0,48,null,null,12,49]
//输出：1
//
//
//
//
// 提示：
//
//
// 树中节点的数目范围是 [2, 10⁴]
// 0 <= Node.val <= 10⁵
//
//
//
//
// 注意：本题与 783 https://leetcode-cn.com/problems/minimum-distance-between-bst-
//nodes/ 相同
//
// Related Topics 树 深度优先搜索 广度优先搜索 二叉搜索树 二叉树 👍 438 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */
//? 中序遍历辅助数组呗
function getMinimumDifference(root: TreeNode | null): number {

    function recur(root) {
        if (root === null) return
        recur(root.left)
        inorder.push(root.val)
        recur(root.right)
    }
    let inorder : number[] = []
    recur(root)
    let minGap : number = Infinity
    for (let i = 0; i < inorder.length - 1; i ++) {
        if (Math.abs(inorder[i] - inorder[i + 1]) < minGap) {
            minGap = Math.abs(inorder[i] - inorder[i + 1])
        }
    }
    return minGap
};
//leetcode submit region end(Prohibit modification and deletion)
//? 递归中解决
function getMinimumDifference2(root: TreeNode | null): number {
    let preNode: TreeNode | null= null;
    let resMin: number = Infinity;
    function recur(root: TreeNode | null): void {
        if (root === null) return;
        recur(root.left);
        if (preNode !== null) {
            resMin = Math.min(resMin, root.val - preNode.val);
        }
        preNode = root;
        recur(root.right);
    }
    recur(root);
    return resMin;
};
//? 迭代法
function getMinimumDifference3(root: TreeNode | null): number {
    const helperStack: TreeNode[] = [];
    let curNode: TreeNode | null = root;
    let resMin: number = Infinity;
    let preNode: TreeNode | null = null;
    while (curNode !== null || helperStack.length > 0) {
        if (curNode !== null) {
            helperStack.push(curNode);
            curNode = curNode.left;
        } else {
            curNode = helperStack.pop()!;
            if (preNode !== null) {
                resMin = Math.min(resMin, curNode.val - preNode.val);
            }
            preNode = curNode;
            curNode = curNode.right;
        }
    }
    return resMin;
};
